(* Content-type: application/mathematica *)

(*** Wolfram Notebook File ***)
(* http://www.wolfram.com/nb *)

(* CreatedBy='Mathematica 7.0' *)

(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
NotebookFileLineBreakTest
NotebookDataPosition[       145,          7]
NotebookDataLength[     17000,        450]
NotebookOptionsPosition[     16175,        422]
NotebookOutlinePosition[     16513,        437]
CellTagsIndexPosition[     16470,        434]
WindowFrame->Normal*)

(* Beginning of Notebook Content *)
Notebook[{
Cell["\<\
Input coordinates - watch out : mathematica expcects {x, y}, but the (pixel) \
coordinates are {x, height - y}\
\>", "Text",
 CellChangeTimes->{{3.555996523915406*^9, 3.5559965555927896`*^9}}],

Cell[BoxData[
 RowBox[{"\[IndentingNewLine]", 
  RowBox[{
   RowBox[{
    RowBox[{"test_coords", "=", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"508", ",", "356"}], "}"}], ",", "\[IndentingNewLine]", 
       RowBox[{"{", 
        RowBox[{"247", ",", "456"}], "}"}], ",", "\[IndentingNewLine]", 
       RowBox[{"{", 
        RowBox[{"388", ",", "673"}], "}"}], ",", "\[IndentingNewLine]", 
       RowBox[{"{", 
        RowBox[{"613", ",", "575"}], "}"}], ",", "\[IndentingNewLine]", 
       RowBox[{"{", 
        RowBox[{"1047", ",", "407"}], "}"}], ",", "\[IndentingNewLine]", 
       RowBox[{"{", 
        RowBox[{"997", ",", "467"}], "}"}], ",", "\[IndentingNewLine]", 
       RowBox[{"{", 
        RowBox[{"847", ",", "173"}], "}"}]}], "}"}]}], ";"}], 
   "\[IndentingNewLine]", 
   RowBox[{
    RowBox[{"easy", "=", 
     RowBox[{"{", "\[IndentingNewLine]", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"1701.00000", ",", "1482.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"992.00000", ",", "135.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"962.00000", ",", "403.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"1431.00000", ",", "344.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"541.00000", ",", "735.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"1528.00000", ",", "1034.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"1411.00000", ",", "2222.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"1492.00000", ",", "2415.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"1391.00000", ",", "2569.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"886.00000", ",", "2708.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"1734.00000", ",", "2492.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"2509.00000", ",", "2191.00000"}], "}"}]}], "\n", "}"}]}], 
    ";"}], "\[IndentingNewLine]", 
   RowBox[{
    RowBox[{"coords", "=", 
     RowBox[{"{", "\[IndentingNewLine]", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"478.00000", ",", "100.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"420.00000", ",", "179.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"471.00000", ",", "248.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"333.00000", ",", "341.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"79.00000", ",", "333.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"11.00000", ",", "537.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"75.00000", ",", "572.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"217.00000", ",", "665.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"205.00000", ",", "719.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"134.00000", ",", "868.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"158.00000", ",", "895.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"605.00000", ",", "296.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"621.00000", ",", "357.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"478.00000", ",", "421.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"409.00000", ",", "446.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"409.00000", ",", "527.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"442.00000", ",", "534.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"469.00000", ",", "616.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"591.00000", ",", "483.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"672.00000", ",", "426.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"597.00000", ",", "902.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"665.00000", ",", "814.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"779.00000", ",", "867.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"846.00000", ",", "743.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"602.00000", ",", "387.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"275.00000", ",", "543.00000"}], "}"}], ",", 
       "\[IndentingNewLine]", 
       RowBox[{"{", 
        RowBox[{"326.00000", ",", "434.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"221.00000", ",", "87.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"107.00000", ",", "233.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"414.00000", ",", "713.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"476.00000", ",", "701.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"606.00000", ",", "706.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"597.00000", ",", "646.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"621.00000", ",", "552.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"766.00000", ",", "567.00000"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"575.00000", ",", "596.00000"}], "}"}]}], 
      "\[IndentingNewLine]", "}"}]}], ";"}], 
   "\[IndentingNewLine]"}]}]], "Input",
 CellChangeTimes->{{3.5556068966459093`*^9, 3.555606982577791*^9}, {
   3.555607058496656*^9, 3.555607105356813*^9}, {3.555607353613246*^9, 
   3.555607357689107*^9}, {3.55560774800062*^9, 3.555607874488392*^9}, {
   3.555607996049828*^9, 3.555607997410343*^9}, {3.555608031654331*^9, 
   3.555608039767159*^9}, {3.5556081250015574`*^9, 3.555608127692309*^9}, 
   3.5556081684145403`*^9, {3.555608208551832*^9, 3.5556082118028316`*^9}, 
   3.555608257781632*^9, {3.555608335503907*^9, 3.555608347588635*^9}, {
   3.5556083814607153`*^9, 3.555608383242675*^9}, {3.555608454206779*^9, 
   3.555608473807564*^9}, {3.5556085406114683`*^9, 3.555608541117979*^9}, 
   3.555608623315061*^9, {3.555608956109027*^9, 3.555609037218486*^9}, {
   3.55592662486287*^9, 3.55592665392994*^9}, {3.555926709606975*^9, 
   3.5559267697583847`*^9}, {3.555931040227755*^9, 3.555931054411628*^9}, {
   3.5559311398876753`*^9, 3.555931140077004*^9}, {3.5559311914355593`*^9, 
   3.555931202702804*^9}, {3.5559965127165728`*^9, 3.5559965188071203`*^9}, {
   3.5559965677118883`*^9, 3.5559965810799847`*^9}, {3.556344693528586*^9, 
   3.55634469496611*^9}, {3.556344850207337*^9, 3.556344850730298*^9}, {
   3.556345245458449*^9, 3.5563452583601418`*^9}, {3.55634589225324*^9, 
   3.556345907882036*^9}, {3.556345955402718*^9, 3.5563460509507008`*^9}, 
   3.5563461039545307`*^9}],

Cell["Define dimenions", "Text",
 CellChangeTimes->{{3.556346107007827*^9, 3.5563461108383713`*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"height", "=", "1024"}], ";", 
  RowBox[{"width", "=", "973"}], ";"}]], "Input"],

Cell["Read in File", "Text",
 CellChangeTimes->{3.556346045467058*^9}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"hard", "=", 
   RowBox[{"Import", "[", 
    RowBox[{"\"\<hard.txt\>\"", ",", " ", "\"\<CSV\>\""}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"easy", "=", 
   RowBox[{"Import", "[", 
    RowBox[{"\"\<easy.txt\>\"", ",", " ", "\"\<CSV\>\""}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"problem", "=", "hard"}], ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"transCoords", " ", "=", " ", 
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{
       RowBox[{
        RowBox[{"problem", "[", 
         RowBox[{"[", 
          RowBox[{"i", ",", "1"}], "]"}], "]"}], "*", "width"}], ",", " ", 
       RowBox[{
        RowBox[{"(", 
         RowBox[{"1", "-", 
          RowBox[{"problem", "[", 
           RowBox[{"[", 
            RowBox[{"i", ",", "2"}], "]"}], "]"}]}], ")"}], "*", "height"}]}],
       "}"}], ",", " ", 
     RowBox[{"{", 
      RowBox[{"i", ",", " ", "1", ",", " ", 
       RowBox[{"Length", "[", "problem", "]"}]}], "}"}]}], "]"}]}], 
  ";"}]}], "Input",
 CellChangeTimes->{{3.556346054964025*^9, 3.556346055332261*^9}, {
  3.5563460894891253`*^9, 3.556346098842369*^9}}],

Cell[BoxData[
 RowBox[{"lp", "=", 
  RowBox[{"ListPlot", "[", "transCoords", "]"}]}]], "Input",
 CellChangeTimes->{{3.555606984669512*^9, 3.555606991344845*^9}, {
  3.555607887901289*^9, 3.55560790769103*^9}, {3.555607938798436*^9, 
  3.555607940155889*^9}, {3.555649648348131*^9, 3.5556496495301123`*^9}}],

Cell["\<\
Find a solution which is ' close to the minimum'
Mathematica 8 comes with new methods for ' FindShortestTour'. One of them \
will find the true minimum.\
\>", "Text",
 CellChangeTimes->{{3.5559966135543203`*^9, 3.555996653209433*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"sol", "=", 
   RowBox[{"FindShortestTour", "[", "problem", "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"hard", "[", 
   RowBox[{"[", 
    RowBox[{"Last", "[", "sol", "]"}], "]"}], "]"}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"transCoords", "[", 
   RowBox[{"[", 
    RowBox[{"Last", "[", "sol", "]"}], "]"}], "]"}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"Show", "[", 
  RowBox[{
   RowBox[{"Graphics", "[", 
    RowBox[{"Line", "[", "%", "]"}], "]"}], ",", "lp"}], "]"}]}], "Input",
 CellChangeTimes->{{3.55560856545892*^9, 3.555608576720112*^9}, {
   3.555649661212661*^9, 3.55564969348341*^9}, 3.5559268384258547`*^9, {
   3.5559312094613647`*^9, 3.555931216649598*^9}, {3.556013485415979*^9, 
   3.556013525094365*^9}, {3.5563461200600348`*^9, 3.556346127417852*^9}}],

Cell["Analytic Solution", "Text",
 CellChangeTimes->{{3.556013557562059*^9, 3.556013561203206*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"sol", "=", 
   RowBox[{"FindShortestTour", "[", 
    RowBox[{"problem", ",", " ", 
     RowBox[{"Method", "\[Rule]", "\"\<IntegerLinearProgramming\>\""}]}], 
    "]"}]}], ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"transCoords", "[", 
   RowBox[{"[", 
    RowBox[{"Last", "[", "sol", "]"}], "]"}], "]"}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"Show", "[", 
  RowBox[{
   RowBox[{"Graphics", "[", 
    RowBox[{"Line", "[", "%", "]"}], "]"}], ",", "lp"}], "]"}]}], "Input",
 CellChangeTimes->{
  3.556344866816435*^9, 3.556345165834113*^9, {3.556346157585659*^9, 
   3.556346158157487*^9}}],

Cell["\<\
Save to File - artificially add first element at the end of the solution list\
\
\>", "Text",
 CellChangeTimes->{{3.556345225513605*^9, 3.556345233721352*^9}, {
  3.556346172706438*^9, 3.556346174123897*^9}, {3.5563462835126047`*^9, 
  3.556346296337178*^9}}],

Cell[BoxData[
 RowBox[{"Join", "[", 
  RowBox[{
   RowBox[{"problem", "[", 
    RowBox[{"[", 
     RowBox[{"Last", "[", "sol", "]"}], "]"}], "]"}], " ", ",", 
   RowBox[{"{", 
    RowBox[{
     RowBox[{"problem", "[", 
      RowBox[{"[", 
       RowBox[{"Last", "[", "sol", "]"}], "]"}], "]"}], "[", 
     RowBox[{"[", "1", "]"}], "]"}], "}"}]}], "]"}]], "Input",
 CellChangeTimes->{{3.556346344813345*^9, 3.5563463509384537`*^9}, {
  3.556346398022625*^9, 3.556346405851675*^9}, {3.556346440819948*^9, 
  3.55634644220709*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"Export", "[", 
   RowBox[{"\"\<solution.csv\>\"", ",", 
    RowBox[{"Join", "[", 
     RowBox[{
      RowBox[{"problem", "[", 
       RowBox[{"[", 
        RowBox[{"Last", "[", "sol", "]"}], "]"}], "]"}], " ", ",", 
      RowBox[{"{", 
       RowBox[{
        RowBox[{"problem", "[", 
         RowBox[{"[", 
          RowBox[{"Last", "[", "sol", "]"}], "]"}], "]"}], "[", 
        RowBox[{"[", "1", "]"}], "]"}], "}"}]}], "]"}], ",", " ", 
    "\"\<CSV\>\""}], "]"}], ";"}]], "Input",
 CellChangeTimes->{{3.556345265425761*^9, 3.556345310458547*^9}, {
   3.55634534615095*^9, 3.556345352782631*^9}, {3.5563453980535917`*^9, 
   3.5563454459744167`*^9}, {3.556345476101424*^9, 3.556345476957589*^9}, {
   3.556345632439445*^9, 3.556345696223239*^9}, {3.556345727313447*^9, 
   3.556345749628221*^9}, {3.556346213750105*^9, 3.556346220317754*^9}, 
   3.5563462991420813`*^9, 3.556346329490107*^9, {3.556346422229588*^9, 
   3.5563464516221333`*^9}}],

Cell["Test for 30 random locations", "Text",
 CellChangeTimes->{{3.5559966662018137`*^9, 3.55599668455245*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"max", "=", "100"}], ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"randCoords", " ", "=", " ", 
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{
       RowBox[{"Random", "[", 
        RowBox[{"Integer", ",", " ", "1024"}], "]"}], ",", " ", 
       RowBox[{"Random", "[", 
        RowBox[{"Integer", ",", "1024"}], "]"}]}], "}"}], ",", " ", 
     RowBox[{"{", 
      RowBox[{"i", ",", " ", "1", ",", " ", "max"}], "}"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"lp", "=", 
  RowBox[{"ListPlot", "[", 
   RowBox[{"randCoords", ",", " ", 
    RowBox[{"PlotRange", "\[Rule]", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"0", ",", "1024"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"0", ",", "1024"}], "}"}]}], "}"}]}]}], 
   "]"}]}], "\[IndentingNewLine]", 
 RowBox[{"Timing", "[", 
  RowBox[{"sol", "=", 
   RowBox[{"FindShortestTour", "[", 
    RowBox[{"randCoords", ",", " ", 
     RowBox[{"Method", "\[Rule]", "\"\<SimulatedAnnealing\>\""}]}], "]"}]}], 
  "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"randCoords", "[", 
   RowBox[{"[", 
    RowBox[{"Last", "[", "sol", "]"}], "]"}], "]"}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"Show", "[", 
  RowBox[{
   RowBox[{"Graphics", "[", 
    RowBox[{"Line", "[", "%", "]"}], "]"}], ",", " ", "lp"}], 
  "]"}], "\[IndentingNewLine]", 
 RowBox[{"distSA", "=", " ", 
  RowBox[{
   RowBox[{"sol", "[", 
    RowBox[{"[", "1", "]"}], "]"}], "//", "N"}]}], "\[IndentingNewLine]", 
 RowBox[{"Timing", "[", 
  RowBox[{"sol", "=", 
   RowBox[{"FindShortestTour", "[", 
    RowBox[{"randCoords", ",", " ", 
     RowBox[{"Method", "\[Rule]", "\"\<IntegerLinearProgramming\>\""}]}], 
    "]"}]}], "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"randCoords", "[", 
   RowBox[{"[", 
    RowBox[{"Last", "[", "sol", "]"}], "]"}], "]"}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"Show", "[", 
  RowBox[{
   RowBox[{"Graphics", "[", 
    RowBox[{"Line", "[", "%", "]"}], "]"}], ",", " ", "lp"}], 
  "]"}], "\[IndentingNewLine]", 
 RowBox[{"distILP", "=", " ", 
  RowBox[{
   RowBox[{"sol", "[", 
    RowBox[{"[", "1", "]"}], "]"}], "//", "N"}]}], "\[IndentingNewLine]", 
 RowBox[{"Print", "[", 
  RowBox[{
  "\"\<SA solution: \>\"", ",", "distSA", ",", "\"\<, ILP solution: \>\"", 
   ",", "distILP", ",", "\"\<. Difference: \>\"", ",", 
   RowBox[{"distSA", "-", "distILP"}]}], "]"}]}], "Input",
 CellChangeTimes->{{3.55564906271483*^9, 3.555649125923251*^9}, {
   3.555649219341239*^9, 3.555649233420025*^9}, {3.555649286676404*^9, 
   3.5556493929267693`*^9}, {3.555649436276862*^9, 3.555649442350182*^9}, {
   3.55564947527404*^9, 3.555649492724921*^9}, {3.555649608035975*^9, 
   3.5556496205804453`*^9}, {3.555661134932103*^9, 3.5556611352682323`*^9}, {
   3.5556612334311743`*^9, 3.555661233858233*^9}, {3.5556612820051394`*^9, 
   3.555661307697669*^9}, {3.5556614675686617`*^9, 3.555661492049075*^9}, {
   3.5556615527429247`*^9, 3.55566155627883*^9}, {3.555661690565794*^9, 
   3.555661717381937*^9}, {3.555996767182621*^9, 3.555996768757552*^9}, {
   3.556013403569366*^9, 3.556013434068922*^9}, 3.556013567454837*^9, 
   3.556013710375484*^9, {3.556013744992167*^9, 3.5560137810778017`*^9}, {
   3.5560138123193703`*^9, 3.556013971567997*^9}, {3.5560140079529257`*^9, 
   3.55601400804853*^9}}]
},
WindowSize->{1272, 942},
WindowMargins->{{1280, Automatic}, {0, Automatic}},
FrontEndVersion->"8.0 for Linux x86 (64-bit) (November 7, 2010)",
StyleDefinitions->"Default.nb"
]
(* End of Notebook Content *)

(* Internal cache information *)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[545, 20, 202, 4, 30, "Text"],
Cell[750, 26, 6518, 148, 449, "Input"],
Cell[7271, 176, 100, 1, 30, "Text"],
Cell[7374, 179, 114, 3, 30, "Input"],
Cell[7491, 184, 70, 1, 30, "Text"],
Cell[7564, 187, 1189, 35, 88, "Input"],
Cell[8756, 224, 306, 5, 30, "Input"],
Cell[9065, 231, 244, 5, 49, "Text"],
Cell[9312, 238, 846, 22, 88, "Input"],
Cell[10161, 262, 99, 1, 30, "Text"],
Cell[10263, 265, 637, 18, 69, "Input"],
Cell[10903, 285, 269, 6, 30, "Text"],
Cell[11175, 293, 528, 14, 30, "Input"],
Cell[11706, 309, 982, 22, 30, "Input"],
Cell[12691, 333, 111, 1, 30, "Text"],
Cell[12805, 336, 3366, 84, 240, "Input"]
}
]
*)

(* End of internal cache information *)
